class Solution {
public:
    int partion(vector<int>& nums, int left, int right)
    {
        int mid = (left + right) >> 1;
        swap(nums[left], nums[mid]);

        int n = nums.size();
        int key = nums[left];
        int l = left + 1, r = right;
        while(true)
        {
            while(l <= r && nums[l] < key) ++l;
            while(l <= r && nums[r] > key) --r;

            if(l >= r) break;
            swap(nums[l++], nums[r--]);
        }

        swap(nums[left], nums[r]);
        return r;
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int target = n - k;

        int l = 0, r = n - 1;
        while(true)
        {
            int p = partion(nums, l, r);
            if(p == target)
                return nums[p];
            else if(p > target)
                r = p - 1;
            else
                l = p + 1;
        }
        return -1;
    }
};

